/*
 * s_linklist.c
 *
 *  Created on: 2017年10月18日
 *      Author: simon
 */

#include "../include/s_linklist.h"


//创建链表
S_PNODE s_create_linklist(void)
{
	int num;
	int i;
	S_PNODE PHead = (S_PNODE)malloc(1*sizeof(S_NODE));
	if(!PHead) {
		printf("HNode allocation failure\n");
		exit(EXIT_FAILURE);
	}
	S_PNODE PTail = PHead;
	PHead->pNext = NULL;
	printf("please input the length of list:");
	scanf("%d",&num);
	for(i=0;i<num;i++) {
		S_PNODE p = (S_PNODE)malloc(1*sizeof(S_NODE));
		if(!p) {
			printf("Node allocation failure\n");
			exit(EXIT_FAILURE);
		}
		printf("please input the value(%d) of list: ",i+1);
		scanf("%d",&p->data);
		PTail->pNext = p;
		PTail->pNext->pNext = NULL;
		PTail = p;
		p = NULL;
	}
	printf("allocation success\n");
	return PHead;
}
//遍历链表，打印
void s_print_linklist1(S_PNODE PHead)
{
	if(PHead == NULL) {
		printf("Linklist empty\n");
		exit(EXIT_FAILURE);
	}
	S_PNODE p = PHead->pNext;
	while(p != NULL) {
		printf("%d\t",p->data);
		p = p->pNext;
	}
	p = NULL;
	printf("\n");
	return ;
}
/**
 * 假如要在节点2的前面插入节点p，我们首先要找到节点2的前驱节点1，假设现在q指针指向节点1，则
（1）p->pNext=q->pNext;
（2）q->pNext=p;
*/
void s_insert_val_linklist(S_PNODE PHead,int pos,int data)
{
	if(PHead == NULL) {
		printf("PHead is empty\n");
		exit(EXIT_FAILURE);
	}
	if(pos < 1) {
		printf("insert pos < 1\n");
		exit(EXIT_FAILURE);
	}
	int index = 0;
	S_PNODE q = PHead;
	while(q != NULL&&index < pos-1) {
		index ++;
		//想插入的位置超出的范围。
		if(q->pNext == NULL) {
			break;
		}
		q = q->pNext;
	}
	if(q->pNext == NULL||index == (pos - 1)) {
		S_PNODE p = (S_PNODE)malloc(1*sizeof(S_NODE));
		p->data = data;
		p->pNext = q->pNext;
		q->pNext = p;
		p = q = NULL;
		printf("insert success\n");
	}
}
//插入节点
void s_insert_node_linklist(S_PNODE PHead,S_PNODE node,int pos)
{
	int index = 0;
	if(PHead == NULL&&PHead->pNext == NULL) {
		printf("Linklist is empty\n");
		return ;
	}
	S_PNODE p = PHead;
	while( p->pNext != NULL&&index <(pos-1)) {
		index++;
		p = p->pNext;
	}
	if(p->pNext == NULL||index == (pos-1)) {
		node->pNext = p->pNext;
		p->pNext = node;
		p = NULL;
	}
	return ;
}
//链表的长度
int s_length_linklist(S_PNODE PHead)
{
	if(PHead == NULL) {
		printf("Linklist is empty\n");
		return 0;
	}
	int length = 0;
	S_PNODE p = PHead->pNext;
	while(p != NULL) {
		length++;
		p = p->pNext;
	}
	p = NULL;
	return length;
}
void s_selectsort_linklist(S_PNODE PHead)
{
	if(PHead == NULL || PHead->pNext == NULL) {
		printf("Linklist is empty\n");
		exit(EXIT_FAILURE);
	}
	S_PNODE p = PHead->pNext;;
	S_PNODE q;
	int i,j;
	int temp;
	int length = s_length_linklist(PHead);
	for(i = 0;i < length-1;i++,p = p->pNext) {
		for(j = i+1,q = p->pNext; j<length;j++,q = q->pNext) {
			if(q->data < p->data) {
				temp = q->data;
				q->data = p->data;
				p->data = temp;
			}
		}
	}
}

S_PNODE s_reversed_linklist1(S_PNODE PHead)
{
	if(PHead->pNext == NULL || PHead == NULL) {
		printf("Linklist is empty\n");
		exit(EXIT_FAILURE);
	}
	S_PNODE head = PHead->pNext;
	S_PNODE next;
	S_PNODE prev = NULL;
	while(head != NULL) {
		next = head->pNext;
		head->pNext = prev;
		prev = head;
		head = next;
	}
	return prev;
}
S_PNODE s_reversed_linklist2(S_PNODE head)
{
	S_PNODE PNewHead;
	if(head == NULL || head->pNext == NULL) {
		return head;
	}
	PNewHead = s_reversed_linklist2(head->pNext);
	head->pNext->pNext = head;
	head->pNext = NULL;
	return PNewHead;
}
S_PNODE s_find_linklist(S_PNODE PHead,int pos)
{
	if(PHead == NULL||PHead->pNext == NULL) {
		printf("Linklist is empty\n");
		return NULL;
	}
	S_PNODE p = PHead;
	int index = 0;
	while(p != NULL&& index <(pos)) {
		index++;
		p = p->pNext;
	}
	if(index == pos) {
		return p;
	}
	printf("Not found\n");
	return NULL;
}
